Programmable integrated circuits (ICs) are often used to implement digital logic operations according to user configurable input. Example programmable ICs include complex programmable logic devices (CPLDs) and field programmable gate arrays (FPGAs). CPLDs often include several function blocks that are based on programmable logic array (PLA) architecture with sum-of-products logic. A configurable interconnect matrix transmits signals between the function blocks.
An example FPGA includes an array of configurable logic blocks (CLBs) and a ring or columns of programmable input/output blocks (IOBs). The CLBs and IOBs are interconnected by a programmable interconnect structure (routing resources). The CLBs, IOBs, and interconnect structure are typically programmed by loading a stream of configuration data (bitstream) into internal configuration memory cells that determine how the CLBs, IOBs, and interconnect structure function. The configuration bitstream may be read from an external memory, conventionally an external integrated circuit memory EEPROM, EPROM, PROM, and the like, though other types of memory may be used. The collective states of the individual memory cells determine the function of the FPGA. A specific type of FPGA uses a look-up-table (LUT)-based CLB. The configuration memory provides input values to a number of multiplexers that are controlled by inputs to the CLB.
A conventional design process for an integrated circuit, such as an ASIC or an FPGA implementation begins with the creation of the design. The design specifies the function of a circuit at a schematic or logic level and may be represented using various hardware description languages (e.g., VHDL, ABEL, or Verilog) or schematic capture programs. The design is synthesized to produce a logical network list (“netlist”), and the synthesized design is mapped onto primitive components within the target device (e.g., programmable logic blocks of an FPGA).
Following mapping, placement of the components of the synthesized and mapped design is then performed for the target device. During placement, each mapped component of the design is assigned to a physical position on the chip. The placer attempts to place connected design objects in close physical proximity to one another in order to conserve space and increase the probability that the desired interconnections between components will be successfully completed by the router. Placing connected components close to one another also generally improves the performance of the circuit since long interconnect paths are associated with excess capacitance and resistance, resulting in longer delays and greater power consumption.
Specified connections between components of the design are routed within the target device for the placed components. The routing process specifies physical wiring resources that will be used to conduct signals between pins of placed components of the design. For each connection specified in the design, the routing process allocates wire resources necessary to complete the connection. As used herein, the selection and assignment of wire resources in connecting the output pin of one component to the input pin of another component is referred to as routing a net. When nets have been routed using most or all of the wiring resources in a given area, the area is generally referred to as congested, which creates competition for the remaining wiring resources in the area or makes routing of additional nets in the area impossible.
Most current programmable integrated circuit (IC) routing tools are based on a negotiated congestion resolution scheme. In a typical implementation, for example, the Pathfinder algorithm, nets are routed sequentially. A path through the programmable resources of the programmable IC is determined by an expansion of possible paths from a source to a destination. In the process of routing a net, other nets may have been already routed on the wire resources required to route the unrouted signal. When two nets use the same resource, it is known as congestion. During expansion, a cost of resource use for each possible path is tracked and maintained during expansion of the possible paths to reflect the demand for use of each resource for routing. In response to two or more nets attempting to route with the same resource, the cost of the congested resource is increased and the conflicting nets are rerouted. The increased resource cost encourages any subsequently routed nets to be routed using other (less expensive) resources. Nets having limited routing resources available to provide a possible path from the source to the destination may use the congested resources if those resources provide the least expensive path in spite of their increased cost. In this manner, nets are iteratively routed while adjusting resource costs to find a solution.
Because the routing of each net increases the cost of some resources, the routing of subsequently routed nets may be affected. The final routing result is determined, in part, by the order in which nets are routed. Therefore, in order to produce deterministic results, the nets must be routed in the same order every time routing is performed.
However, when two or more nets are routed in parallel, it can be difficult to control the order in which nets are routed due to unexpected or critical dependencies known as race conditions. For example, when a processor performs a read of a memory, the time to complete the memory access may depend on the number of other processes attempting to perform read operations. The order in which concurrently routed nets are routed may be similarly affected by memory access delays as the processors attempt to read and update congestion data.
The disclosed embodiments may address one or more of the above issues.